// include/maze_bfs.h
#pragma once

#include <algorithm>
#include <queue>
#include <vector>

#ifndef MAZE_CELL_DECLARED
#define MAZE_CELL_DECLARED
namespace Maze {

  /**
   * @brief 迷宫中的网格坐标。
   *
   *  - row 表示行索引，从 0 开始。
   *  - col 表示列索引，从 0 开始。
   */
  struct Cell {
    int row{0};
    int col{0};

    friend constexpr bool operator==(const Cell& lhs, const Cell& rhs) noexcept {
      return lhs.row == rhs.row && lhs.col == rhs.col;
    }
  };

} // namespace Maze
#endif // MAZE_CELL_DECLARED

namespace Maze {

  /**
   * @brief 使用广度优先搜索寻找从 (0,0) 至 (rows-1, cols-1) 的最短路径。
   *
   * @param maze 仅包含 0/1 的二维网格，0 表示可走，1 表示障碍。
   * @return 首次到达终点的路径，若无路径则返回空向量。
   *
   * @note 通过前驱数组回溯路径，保证输出最短解。
   */
  inline auto breadthFirstSearch(const std::vector<std::vector<int>>& maze)
      -> std::vector<Cell> {
    if (maze.empty() || maze[0].empty() || maze[0][0] == 1) {
      return {};
    }

    const int rows = static_cast<int>(maze.size());
    const int cols = static_cast<int>(maze[0].size());
    std::vector<bool> visited(rows * cols, false);
    std::vector<int> parent(rows * cols, -1);
    std::queue<Cell> q;

    /**
     * @brief 辅助函数：判断坐标是否可行。
     */
    auto isValid = [&](int r, int c) noexcept {
      return r >= 0 && c >= 0 && r < rows && c < cols && maze[r][c] == 0;
    };

    /**
     * @brief 入队并记录前驱信息。
     */
    auto enqueue = [&](int r, int c, int prevIdx) {
      if (!isValid(r, c)) {
        return;
      }
      const int idx = r * cols + c;
      if (visited[idx]) {
        return;
      }
      visited[idx] = true;
      parent[idx] = prevIdx;
      q.push({r, c});
    };

    enqueue(0, 0, -2); ///< -2 作为起点标记。

    constexpr int DR[4] = {0, 1, 0, -1};
    constexpr int DC[4] = {1, 0, -1, 0};

    while (!q.empty()) {
      const Cell current = q.front();
      q.pop();

      if (current.row == rows - 1 && current.col == cols - 1) {
        std::vector<Cell> path;
        for (int idx = current.row * cols + current.col;
             idx != -2; idx = parent[idx]) {
          path.push_back({idx / cols, idx % cols});
        }
        std::reverse(path.begin(), path.end()); ///< 回溯后需倒序得到正向路径。
        return path;
      }

      const int curIdx = current.row * cols + current.col;
      for (int i = 0; i < 4; ++i) {
        enqueue(current.row + DR[i], current.col + DC[i], curIdx);
      }
    }

    return {}; ///< 队列耗尽仍未抵达终点，表示无解。
  }

} // namespace Maze